Search for: All records

Proof-of-Work (PoW) is one of the fundamental and widely-used consensus algorithms in blockchains. In PoW, nodes compete to receive the mining reward by trying to be the first to solve a puzzle. Despite its fairness and wide availability, traditional PoW incurs extreme computational and energy waste over the blockchain. This waste is considered to be one of the biggest problems in PoW-based blockchains and cryptocurrencies. In this work, we propose a new useful PoW called Proof-of-Useful-Randomness (PoUR) that mitigates the energy waste by incorporating pre-computed (disclosable) randomness into the PoW. The key idea is to inject special randomness into puzzles via algebraic commitments that can be stored and later disclosed. Unlike the traditional wasteful PoWs, our approach enables pre-computed commitments to be utilized by a vast array of public-key cryptography methods that require offline-online processing (e.g., digital signature, key exchange, zero-knowledge protocol). Moreover, our PoW preserves the desirable properties of the traditional PoW and therefore does not require a substantial alteration in the underlying protocol. We showed the security of our PoW, and then fully implemented it to validate its significant energy-saving capabilities. 

Audit logs play a crucial role in the security of computer systems and are targeted by the attackers due to their forensic value. Digital signatures are essential tools to ensure the authentication/integrity of logs with public verifiability and nonrepudiation. Especially, forward-secure and aggregate signatures (FAS) offer compromise-resiliency and append-only features such that an active attacker compromising a computer cannot tamper or selectively delete the logs collected before the breach. Despite their high-security, existing FAS schemes can only sign a small pre-defined number (K) of logs, and their key-size/computation overhead grows linearly with K. These limitations prevent a practical adoption of FAS schemes for digital forensics. In this paper, we created new signatures named COmpact and REsilient (CORE) schemes, which are (to the best of our knowledge) the first FAS that can sign (practically) unbounded number of messages with only a sub-linear growth in the keysize/computation overhead. Central to CORE is the creation of a novel K-time signature COREKBase that has a small-constant key generation overhead and public key size. We then develop CORE-MMM that harnesses COREK Base via forward-secure transformations. We showed that CORE-MMM significantly outperforms its alternatives for essential metrics. For instance, CORE-MMM provides more than two and one magnitudes faster key updates and smaller signatures, respectively, with smaller private keys. CORE-MMM also offers extra efficiency when the same messages are signed with evolving keys. We formally prove that CORE schemes are secure. Our analysis indicates that CORE schemes are ideal tools to enhance the trustworthiness of digital forensic applications.